package com.hit.basmath.interview.we_meet.bytedance.news;

import java.util.Stack;

/**
 * 题目：找到每个元素后面第一个比它大的数
 * <p>
 * 有n(n<=10^8)个整数的无序数组，找到每个元素后面第一个比它大的数，时间复杂度o(n)
 * <p>
 * 输入 ： 5，1，2， 8，9，2
 * <p>
 * 输出：  8，2，8，9，-1，-1
 */
public class FindFirstLargerRight {

    public int[] findMaxRightWithStack(int[] array) {
        if (array == null) {
            return array;
        }
        int size = array.length;
        int[] result = new int[size];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int index = 1;
        while (index < size) {
            if (!stack.isEmpty() && array[index] > array[stack.peek()]) {
                result[stack.pop()] = array[index];
            } else {
                stack.push(index);
                index++;
            }
        }
        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }
        return result;
    }
}
